package cn.yuemouren.linkedlist;

/**
 * @Author: Timi
 * @Description: 链表
 * @Date: 2020/5/14 8:40
 */
public class LinkedList<T> {

    /**
     * 链表中节点类
     */
    private class Node{
        private T t;
        private Node next;

        public Node(){
            this(null);
        }

        public Node(T t){
            this(t,null);
        }

        public Node(T t,Node next){
            this.t = t;
            this.next = next;
        }
    }

    private Node virtualHead;//虚拟头节点（浪费一个位置，让插入从1开始）
    private int size;

    public LinkedList(){
        virtualHead = new Node();
        size = 0;
    }

    public void addFirst(T t){
        add(0,t);
    }

    public void addLast(T t){
        add(size,t);
    }

    /**
     *  根据索引向链表中插入值
     * @param index
     * @param t
     */
    public void add(int index,T t){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("ADD is fail,index is fail");
        }
        Node prev = virtualHead;
        for(int i = 0; i < index; i++){
            prev = prev.next;
        }
        prev.next = new Node(t,prev.next);
        size++;
    }

    public T getFirst(){
        return get(0);
    }

    public T getLast(){
        return get(size);
    }

    /**
     * 根据索引获取链表中的值
     * @param index
     * @return
     */
    public T get(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("GET t fail,index is fail");
        }
        Node prev = virtualHead;
        for(int i = 0; i <= index; i++){
            prev = prev.next;
        }
        return prev.t;
    }

    public T modifyFirst(T t){
        return modify(0,t);
    }

    public T modifyLast(T t){
        return modify(size,t);
    }

    /**
     * 根据索引修改节点值
     * @param index
     * @param t
     * @return
     */
    public T modify(int index,T t){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("MODIFY t fail,index is fail");
        }
        Node prev = virtualHead;
        for (int i = 0; i <= index; i++){
            prev = prev.next;
        }
        T res = prev.t;
        prev.t = t;
        return res;
    }

    public T removeFirst(){
        return remove(0);
    }

    public T removeLast(){
        return remove(size);
    }

    /**
     * 根据索引删除节点
     * @param index
     * @return
     */
    public T remove(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("REMOVE t fail,index is fail");
        }
        Node prev = virtualHead;
        for (int i = 0; i < index; i++){
            prev = prev.next;
        }
        Node delNode = prev.next;
        prev.next = delNode.next;
        delNode.next = null;
        size--;
        return delNode.t;
    }

    public T removeElement(T t){
        Node cur = virtualHead.next;
        Node delNode = null;
        while(null != cur){
            if(t.equals(cur.t)){
              break;
            }
            cur = cur.next;
        }
        if(null != cur){
            delNode = cur.next;
            cur = delNode.next;
            delNode.next = null;
            size--;
            return delNode.t;
        }
        return null;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0 ? true : false;
    }

    public boolean contains(T t){
        Node cur = virtualHead.next;
        while (null != cur){
            if(t.equals(cur.t))
                return true;
            cur = cur.next;
        }
        return false;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LinkedList: size = "+size);
        sb.append("[");
        Node prev = virtualHead.next;
        for (int i = 0; i < size; i++){
            sb.append(prev.t);
            prev = prev.next;
            if(i < size-1){
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}
